# (x1, y1, x2, y2)
class Solution:
    def isRectangleCover(self, rectangles: list) -> bool:
        """前面半部分对的,后面半部分时间太长了"""
        bottom_x, bottom_y, top_x, top_y = rectangles[0]
        length = len(rectangles)
        squr = (rectangles[0][2] - rectangles[0][0]) * (rectangles[0][3] - rectangles[0][1])
        for i in range(1, length):
            lists = rectangles[i]
            bottom_x = min(bottom_x, lists[0])
            bottom_y = min(bottom_y, lists[1])
            top_x = max(top_x, lists[2])
            top_y = max(top_y, lists[3])
            squr += (lists[2] - lists[0]) * (lists[3] - lists[1])
        if (top_x - bottom_x) * (top_y - bottom_y) != squr:
            return False
        for i in range(length):
            mid_tar = rectangles[i]
            for j in range(i + 1, length):
                test = rectangles[j]
                if (mid_tar[0] <= test[0] < mid_tar[2] or mid_tar[0] < test[2] <= mid_tar[2]) and \
                        ((test[1] <= mid_tar[1] < test[3]) or (test[1] < mid_tar[3] <= test[3]) or ()):
                    return False
        return True


from collections import defaultdict


class Solution2:
    def isRectangleCover(self, rectangles: list) -> bool:
        squr = 0
        dingdian = defaultdict(int)
        for lists in rectangles:
            squr += (lists[2] - lists[0]) * (lists[3] - lists[1])
            dingdian[(lists[0], lists[1])] += 1
            dingdian[(lists[0], lists[3])] += 1
            dingdian[(lists[2], lists[1])] += 1
            dingdian[(lists[2], lists[3])] += 1
        dingdian_list = []
        for key, value in dingdian.items():
            if value == 2 or value == 4:
                continue
            elif value == 1:
                dingdian_list.append(key)
            else:
                return False
        if len(dingdian_list) != 4:
            return False
        x_list = [i[0] for i in dingdian_list]
        y_list = [i[1] for i in dingdian_list]
        if (max(x_list) - min(x_list)) * (max(y_list) - min(y_list)) != squr:
            return False
        return True


a = Solution2()
print(a.isRectangleCover([[1, 1, 3, 3], [3, 1, 4, 2], [3, 2, 4, 4], [1, 3, 2, 4], [2, 3, 3, 4]]))
print(a.isRectangleCover([[1, 1, 2, 3], [1, 3, 2, 4], [3, 1, 4, 2], [3, 2, 4, 4]]))
print(a.isRectangleCover([[1, 1, 3, 3], [3, 1, 4, 2], [1, 3, 2, 4], [3, 2, 4, 4]]))
print(a.isRectangleCover([[1, 1, 3, 3], [3, 1, 4, 2], [1, 3, 2, 4], [2, 2, 4, 4]]))
print(a.isRectangleCover([[0, 0, 1, 1], [0, 1, 3, 2], [1, 0, 2, 2]]))
print(a.isRectangleCover([[0, 0, 3, 1], [0, 1, 2, 3], [1, 0, 2, 1], [2, 2, 3, 3]]))
